import stack
class Node():
    def __init__(self, ):
        """Constructor for Node"""
        self.left = None
        self.rigth = None
        self.data = None
class BTree():
    def __init__(self,l):
        """Constructor for BTree"""
        assert isinstance(l,(list,tuple))
        # self.root = None
        self.count = 0
#       调用二叉树数据遍历
        if l:
            self.root = self.bulid(l, 0, len(l) - 1)

    def bulid(self,l,min,max):
        self.count += 1
        node = Node()
        minddle = int((min+max)/2)
        node.data = l[minddle]
        if minddle>min:
            node.left = self.bulid(l,min,minddle-1)
        if minddle<max:
            node.rigth = self.bulid(l,minddle+1,max)
        return node

    def find(self,node,data):
        if node.data == data:
            return data
        else:
            if node.left:
                d = self.find(node.left, data)
                if d:
                    return d
            if node.rigth:
                d = self.find(node.rigth, data)
                if d:
                    return d
            return None

    def __len__(self):
        return self.count

    def _foreach(self,node):
        if node is None:
            return
        print(node.data)
        if node.left:
            self._foreach(node.left)
        if node.rigth:
            self._foreach(node.rigth)
    def loop(self):
       return self._foreach(self.root)
if __name__ == '__main__':
    l = [1,2,3,4,5,6,7,8,9,10]
    b_tree = BTree(l)
    b_tree.loop()
    print("===================")
    find = b_tree.find(b_tree.root, 4)
    print("数据存在{}".format(find))
